/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 19:14
 */
public class test_7 {
    public static void main(String[] args) {
        String str = "(}(}";
        int ret = Minbrack(str);
        System.out.println(ret);
    }

    private static int Minbrack(String str) {
        int n = str.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int len = 1; len < n; len++) {
            for (int i = 0; i < n - len; i++) {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                if ((str.charAt(i) == '(' && str.charAt(j) == ')') || (str.charAt(i) == '[' && str.charAt(j) == ']')
                ||(str.charAt(i) == '{' && str.charAt(j) == '}')) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
                } else if ((str.charAt(i) == '(') || (str.charAt(i) == '[') || (str.charAt(i) == '{')) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                } else if ((str.charAt(j) == ')') || (str.charAt(j) == ']') || (str.charAt(j) == '}')) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                }
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
